package developer.算法.回溯.单词搜索;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/4/1 18:04
 * @description 给定一个 m x n 二维字符网格 board
 * 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * <p>
 * 单词必须按照字母顺序，
 * 通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格
 * 。同一个单元格内的字母不允许被重复使用。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 * 示例 2：
 * <p>
 * <p>
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
 * 输出：true
 * 示例 3：
 * <p>
 * <p>
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
 * 输出：false
 */
public class DanCiSouSuo {

    public static void main(String[] args) {
        char[][] example1 = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'},
        };

        Solution3 solution = new Solution3();
        System.out.println(solution.exist(example1, "ABCCED"));
        System.out.println(solution.exist(example1, "SEE"));
        System.out.println(solution.exist(example1, "ABCB"));

    }

    static class Solution3 {
        boolean flag;

        public boolean exist(char[][] board, String word) {
            flag = false;

            int height = board.length;//长度
            int width = board[0].length;


            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (flag) {
                        return flag;
                    }
                    dfs(0,
                            0,
                            board,
                            new int[height][width],
                            new StringBuilder(),
                            word
                    );
                }
            }
            return flag;
        }

        private void dfs(
                int row,
                int column,
                char[][] board,
                int[][] currentSearch,
                StringBuilder currentWord,
                String targetWord
        ) {
            if (flag) {
                return;
            }
            if (currentWord.toString().equals(targetWord)) {
                flag = true;
                return;
            }
            //如果不在表格中 则直接返回
            if (!isInBound(row, column, board)) {
                return;
            }
            int currentCell = currentSearch[row][column];
            if (currentCell == 1) {//说明当前的表格是在搜索中的
                return;
            }
            currentSearch[row][column] = 1;
            char c = board[row][column];
            //如果需要的是一致的
            if (targetWord.charAt(currentWord.length()) == c) {
                currentWord.append(c);
                dfs(row - 1, column, board, currentSearch, currentWord, targetWord);
                dfs(row + 1, column, board, currentSearch, currentWord, targetWord);
                dfs(row, column + 1, board, currentSearch, currentWord, targetWord);
                dfs(row, column - 1, board, currentSearch, currentWord, targetWord);
                currentWord.deleteCharAt(currentWord.length() - 1);
            }

            currentSearch[row][column] = 0;
        }

        private boolean isInBound(int row, int column, char[][] board) {
            if (row < 0) {
                return false;
            }
            if (column < 0) {
                return false;
            }
            int height = board.length;//长度
            int width = board[0].length;

            return row < height && column < width;
        }
    }

    static class Solution {
        boolean result;


        public boolean exist(char[][] board, String word) {
            result = false;
            if (word.isEmpty()) {
                return false;
            }
            List<int[]> startIndexs = new ArrayList<>();//起点的字母（可能有多个)
            char c1 = word.charAt(0);
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    char c = board[i][j];
                    if (c == c1) {
                        startIndexs.add(new int[]{i, j});
                    }
                }
            }
            for (int[] startIndex : startIndexs) {
                if (result) {
                    return true;
                }
                dfs(
                        startIndex[0],
                        startIndex[1],
                        new char[board.length][board[0].length],
                        board,
                        new StringBuilder(),
                        word
                );
            }


            return result;
        }

        private void dfs(int row,//行
                         int col,//列
                         char[][] watched,//遍历过的列表
                         char[][] board,//全部的数据
                         StringBuilder current,
                         String target) {
            if (current.length() == target.length()) {
                result = true;
                return;
            }

            if (!isInTheBird(row, col, board)) {//如果不在表格范围 那么就略过
                return;
            }
            if (watched[row][col] == 2) {//如果已经遍历过了就不用了
                return;
            }
            watched[row][col] = 2;
            char currentChar = board[row][col];

            char needChar = target.charAt(current.length());
            if (needChar == currentChar) {//如果当前格是目标数据那么就进行下一步遍历
                current.append(currentChar);

                dfs(row + 1, col, watched, board, current, target);
                dfs(row - 1, col, watched, board, current, target);
                dfs(row, col + 1, watched, board, current, target);
                dfs(row, col - 1, watched, board, current, target);

                current.deleteCharAt(current.length() - 1);//移除
            }
            watched[row][col] = 0;
        }

        private boolean isInTheBird(int row, int col, char[][] board) {
            int maxRow = board.length;
            int maxCol = board[0].length;

            return row >= 0 && row < maxRow && col >= 0 && col < maxCol;
        }

    }

    class SolutionOfficial {
        public boolean exist(char[][] board, String word) {
            int h = board.length, w = board[0].length;
            boolean[][] visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }

        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
            if (board[i][j] != s.charAt(k)) {
                return false;
            } else if (k == s.length() - 1) {
                return true;
            }
            visited[i][j] = true;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            boolean result = false;
            for (int[] dir : directions) {
                int newi = i + dir[0], newj = j + dir[1];
                if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                    if (!visited[newi][newj]) {
                        boolean flag = check(board, visited, newi, newj, s, k + 1);
                        if (flag) {
                            result = true;
                            break;
                        }
                    }
                }
            }
            visited[i][j] = false;
            return result;
        }
    }

}
